﻿// 0916train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 流浪地球计划在赤道上均匀部署了N个转向发动机，按位置顺序编号为0~N-1。
1、 初始状态都是未启动状态；
2、 “手动启动”和“关联启动”两种方式；
3、如果在时刻1一个发动机被启动，下一个时刻2与之相邻的两个发动机就会被“关联启动”；
4、如果准备启动某个发动机时，它已经被启动了，则什么都不用做；
5、 发动机0与发动机N-1是相邻；

某些发动机在某些时刻进行“手动启动”，最终所有的发动机都会被启动。
哪些发动机最晚被启动呢?

输入描述
第一行两个数字N和E，中间有空格
N代表部署发动机的总个数，E代表计划手动启动的发动机总个数1<N<=1000，1<=E<=1000，E<=N
接下来共E行,每行都是两个数字T和P，中间有空格
T代表发动机的手动启动时刻，P代表此发动机的位置编号。0<=T<=N，0<=P<=N

输出描述
第一行一个数字N，以回车结束N代表最后被启动的发动机个数
第二行N个数字，中间有空格，以回车结束每个数字代表发动机的位置编号，从小到大排序

输入
8 2
0 1
1 7
输出
2
4 5

8 2 总个数total8 手动启动2
0 1 时刻0，编号1
1 7
 */
class Solution01
{
public:
    vector<int>getNext(int top_node)
    {
        vector<int>next_vec;
        if (top_node == 0)
        {
            //前
            next_vec.push_back(total_ - 1);
            //后
            next_vec.push_back(top_node + 1);
        }
        else if (top_node==total_-1)
        {
            //前
            next_vec.push_back(top_node - 1);
            //后
            next_vec.push_back(0);
        }
        else
        {
	        //前
            next_vec.push_back(top_node - 1);
            //后
            next_vec.push_back(top_node + 1);
        }

        return next_vec;
    }

    Solution01(vector<vector<int>>&start_vec, int total_count)
    {
        total_ = total_count;
        //排序，找出最早启动的编号
        //时刻，编号
        sort(start_vec.begin(), start_vec.end(), [](vector<int>& vec_1, vector<int>& vec_2)
        {
        	return vec_1[0] < vec_2[0];
        });

        for (auto&item:start_vec)
        {
            int time = item[0];
            int index = item[1];
            start_map[time].push_back(index);
        }

        //第一批机器开始时间
        int first_start = start_vec[0][0];
        //队列未开始，初始化为启动前一秒
        int curr_time = start_vec[0][0]-1;

        //checked防止重复启动 编号为0~N-1
        vector<int>checked(total_);

        //循环队列
        deque<int>bfs_queue;
        for (auto&index:start_map[first_start])
        {
            //记录第一批出发的机器
            bfs_queue.push_back(index);
            //标记已访问
            checked[index] = true;
        }

        //发动机0与发动机N-1是相邻
        //与之相邻的两个，启动
        while (!bfs_queue.empty())
        {
            curr_time++;

            if (curr_time!=first_start &&start_map.count(curr_time)>0)
            {
                //手动启动的机器
                vector<int>curr_start_v = start_map.at(curr_time);
                for (auto&i:curr_start_v)
                {
                    if (!checked[i])
                    {
                        bfs_queue.push_back(i);
                        //标记已访问
                        checked[i] = true;
                    }
                }
            }

            vector<int>level_vec;
            int q_size = bfs_queue.size();
            for (int i=0; i<q_size; i++)
            {
                int top_node = bfs_queue.front();
                bfs_queue.pop_front();
                level_vec.push_back(top_node);

                vector<int>next_vec = getNext(top_node);

                for (auto&i:next_vec)
                {
	                if (!checked[i])
	                {
                        bfs_queue.push_back(i);
                        //标记已访问
                        checked[i] = true;
	                }
                }
                //q_size 层序结束
            }
            track_v.push_back(level_vec);
            //while (!bfs_queue.empty())
        }

        int track_v_size = track_v.size();
        vector<int>result = track_v[track_v_size - 1];
        //最后启动个数
        cout << result.size() <<endl;
        //最后启动编号 从小到大排序
        sort(result.begin(), result.end());
        int result_size = result.size();
        for (int i=0; i<result_size; i++)
        {
            cout << result[i];
            if (i!=result_size-1)
            {
                cout << ' ';
            }
        }

        //Solution01
    }
private:
    int total_ = 0;
    vector<vector<int>>track_v;
    unordered_map<int, vector<int>>start_map;
};


/*
c 语言有一个库函数Q：char* strstr(const char *haystack，const char*needle)
实现在字符串 haystack 中查找第一次出现字符串 needle 的位置，如果未找到则返回 null
现要求实现一个strstr的增强函数，可以使用带可选段的字符串来模糊查询，
与strstr一样返回首次查找到的字符串位置
可选段使用"[]"标识，表示该位置是可选段中任意一个字符即可满足匹配条件
比如"a[bc]"表示可以匹配"ab"或"ac"
注意目标字符串中可选段可能出现多次

输入描述
与strstr函数Q一样，输入参数是两个字符串指针，分别是源字符串和目标字符串

输出描述
与strstr函数不同，返回的是源字符串中，匹配子字符串相对于源字符串地址的偏移（从0开始计算)，
如果没有匹配返回-1

补充说明：源字符串中必定不包含"["，目标字符串中"[]"必定成对出现，且不会出现嵌套。
输入的字符串长度在[1,100]之间

示例1：
输入：
abcd
b[cd]
输出：
1
说明
相当于是在源字符串中查找bc或者bd，bc子字符串相对于abcd的偏移是1
 */
class Solution02
{
public:
    void backTrack(int level_i)
    {
        int replace_pos_size = replace_pos.size();
        if (level_i == replace_pos_size)
        {
            vector<string>curr_str_v = replace_vec;
            string res;
            int track_i = 0;
            for (auto&pos_i:replace_pos)
            {
                string track_str;
                track_str += track[track_i];
                curr_str_v[pos_i] = track_str;
                track_i++;
            }

            for (auto&str:curr_str_v)
            {
                res += str;
            }

            sub_str_vec.push_back(res);
            return;
        }

        int level = replace_pos[level_i];
        vector<char>level_vec = choose_map[level];

        int level_vec_size = level_vec.size();
        for (int i=0; i<level_vec_size;i++)
        {
            track.push_back(level_vec[i]);
            backTrack(level_i + 1);
            track.pop_back();
        }
        //backTrack
    }

    void getSearch(string&search_str)
    {
        if (search_str.find('[')==string::npos)
        {
            sub_str_vec.push_back(search_str);
            return;
        }
        
    	
        string curr_str;
        bool is_choose = false;
        int chooseIndex = -1;

        int str_size = search_str.size();
        for (int i=0; i< str_size; i++)
        {
            int curr_ch = search_str[i];
	        //a[bc] 匹配"ab"或"ac"
            if (curr_ch=='[')
            {
                is_choose = true;
                //暂存前面的str
                replace_vec.push_back(curr_str);
                curr_str = "";

                //待选的位置推一个空白字符进去
                replace_vec.push_back("");
                //待替换位置，空白字符位置
                chooseIndex = replace_vec.size()-1;
                replace_pos.push_back(chooseIndex);
            }
            else if (curr_ch==']')
            {
                is_choose = false;
            }
            else
            {
                //处理字符
                if (is_choose)
                {
                    choose_map[chooseIndex].push_back(curr_ch);
                }
                else
                {
                    curr_str += curr_ch;
                }
            }
            //for
        }

        if (!curr_str.empty())
        {
            replace_vec.push_back(curr_str);
            curr_str = "";
        }

        //backTrack开始替换
        backTrack(0);
        //getSearch
    }

    int getSubStrPos(string&origin_str, string&sub_str)
    {
        int sub_size = sub_str.size();
        string curr_sub = origin_str.substr(0, sub_size);

        if (curr_sub == sub_str) return 0;
        
        int origin_size = origin_str.size();
        for (int left=1,right=sub_size; right<origin_size; left++,right++)
        {
            string new_sub = curr_sub.substr(1);
            new_sub += origin_str[right];
            curr_sub = new_sub;
            if (curr_sub==sub_str)
            {
                return left;
            }
        }
        return -1;
        //getSubStrPos
    }

    Solution02(string&origin_str, string&search_str)
    {
        //返回首次查找到的字符串位置
        //没有匹配返回-1
        getSearch(search_str);
        
        int res_pos = INT_MAX;

        for (auto&sub_str:sub_str_vec)
        {
            int sub_pos = getSubStrPos(origin_str, sub_str);
            if (sub_pos!=-1 && sub_pos<res_pos)
            {
                res_pos = sub_pos;
            }
        }

        if (res_pos==INT_MAX)
        {
            cout << -1;
            return;
        }

        cout << res_pos;
	    //Solution02
    }
private:
    vector<int>replace_pos; //待替换的位置
    vector<char>track;
    vector<string>sub_str_vec;//已替换好的，search遍历最终结果
    vector<string>replace_vec;//带有替换索引，待替换
    unordered_map<int, vector<char>>choose_map;
};


/*
输入描述
第一行输入为N（N <= 50），N标识二维矩阵的大小 之后N行，每行有N个值，表格矩阵每个位置的值

其中：
-3：妈妈
-2：宝宝
-1：障碍
>=0：糖果数(0表示没有糖果，但是可以走)

输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3

输出
9
 */
class Solution03
{
public:
    void setPos(int row, int col, int level)
    {
        //记录每一个pos层数
        stringstream key_sstream;
        key_sstream << row << ',' << col;

        string key = key_sstream.str();
        pos_map[key] = level;
    }

    int getPos(int row, int col)
    {
        //获取pos层数
        stringstream key_sstream;
        key_sstream << row << ',' << col;

        string key = key_sstream.str();
        return pos_map.at(key);
    }

    void initData(vector<vector<int>>&grid)
    {
        //-3：妈妈 -2：宝宝
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                if (grid[r][c]==-3)
                {
                    //开始位置
                    start_row = r;
                    start_col = c;
                }
                if (grid[r][c]==-2)
                {
	                //终点位置
                    end_row = r;
                    end_col = c;
                }
                //for
            }
            //for
        }

        //initData
    }

    void bfs(
        vector<vector<int>>& grid,
        vector<vector<bool>>&checked,
        deque<vector<int>>&bfs_queue
    )
    {
        int level = 0;
        is_find = false;//最短路径，找到终点退出队列
        while (!bfs_queue.empty())
        {
            level++;
            int q_size = bfs_queue.size();
            for (int i = 0; i < q_size; i++)
            {
                vector<int>top_node = bfs_queue.front();
                bfs_queue.pop_front();

                int top_val = dynamic_vec[top_node[0]][top_node[1]];

                for (auto& dir_vec : DirectionGrid)
                {
                    int curr_r = top_node[0] + dir_vec[0];
                    int curr_c = top_node[1] + dir_vec[1];

                    if (curr_r==end_row && curr_c==end_col)
                    {
                        //终点无糖果，继承
                        dynamic_vec[end_row][end_col] = max(top_val, dynamic_vec[end_row][end_col]);
                        is_find = true;
                        break;//退出方向矩阵
                    }

                    bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                    bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                    //边界不符合要求
                    if (!is_curr_r || !is_curr_c) continue;

                    bool is_visited = checked[curr_r][curr_c];
                    //-1：障碍
                    bool is_available = grid[curr_r][curr_c] != -1;

                    if (!is_visited&&is_available)
                    {
	                    //入队
                        bfs_queue.push_back({ curr_r,curr_c });
                        //标位已访问
                        checked[curr_r][curr_c] = true;
                        //设置节点层数
                        setPos(curr_r, curr_c, level);
                    }

                    //当前dp只能被上一层的节点更新，防止其他层污染
                    if (is_available && getPos(curr_r,curr_c)==level)
                    {
                        int curr_val = top_val + grid[curr_r][curr_c];
                        //更新最大糖果数
                        dynamic_vec[curr_r][curr_c] = max(curr_val, dynamic_vec[curr_r][curr_c]);
                    }

                    //for dir_vec
                }

                //for q_size 层序遍历
            }

            //最短路径，走到终点，退出队列
            if (is_find) return;

            //while (!bfs_queue.empty())
        }
        //bfs
    }


    Solution03(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        vector<vector<bool>>checked(row_size, vector<bool>(col_size,false));
        dynamic_vec = vector<vector<int>>(row_size, vector<int>(col_size));

        initData(grid);

        deque<vector<int>>bfs_queue;
        bfs_queue.push_back({ start_row, start_col });
        //标记已访问
        checked[start_row][start_col] = true;
        setPos(start_row, start_col, 0);

        bfs(grid, checked, bfs_queue);

        if (!is_find)
        {
            cout << -1;
            return;
        }

        cout << dynamic_vec[end_row][end_col];
	    //Solution03
    }
private:
    bool is_find = false;
    int start_row = -1, start_col = -1;
    int end_row = -1, end_col = -1;
    int row_size = 0, col_size = 0;
    unordered_map<string, int>pos_map; //每个点的level
    vector<vector<int>>dynamic_vec;//每个位置最大糖果数
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};

int main()
{
    {
/*
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
*/
        int g_size;
        cin >> g_size;

        vector<vector<int>>grid(g_size, vector<int>(g_size));

        for (int r=0; r<g_size; r++)
        {
            for (int c=0; c<g_size; c++)
            {
                cin >> grid[r][c];
            }
        }
        Solution03 solu(grid);

        return 0;
    }
	{
/*
abcd
b[cd]
*/
        string origin_str, search_str;
        cin >> origin_str >> search_str;

        //string origin_str = "abcd", search_str = "b[cd]b[cd]a";

        Solution02 solu(origin_str, search_str);

        return 0;
	}
/*
8 2
0 1
1 7
*/
    int total, v_size;
    cin >> total >> v_size;

    vector<vector<int>>start_vec;
    for (int i=0; i<v_size; i++)
    {
        vector<int>item_v(2);
        cin >> item_v[0] >> item_v[1];
        start_vec.push_back(item_v);
    }

    Solution01 solu(start_vec, total);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
